/**
   \file  dynamic_barrier.hh
   \brief Defines a thread barrier (aka rendezvous) whose count can change.

   A thread barrier or rendezvous is a synchronization primitive that
   blocks all participating threads until each of them has "arrived" at
   the barrier. Once all threads have reached the barrier, it allows them
   all to proceed from that point on.

   Usually, a barrier is created for a specific number of threads and can
   only be used for that particular number of threads. However, in some
   situations, we would like to be able to change that number. For
   example, some threads may finish up their work and stop participating
   in the barrier. Alternatively, new threads may be spawned that may
   want to join a group of threads participating in a barrier.

   This file defines a class that implements a dynamic barrier as
   described in the preceding paragraph.

   DEVNOTE: Boost.Thread already provides a barrier implementation.
   However, that is a "static" barrier, i.e., one whose thread count is
   fixed at creation time and cannot be changed. Ideally, we would like
   this file's class to be included in Boost.Thread. But for now, it
   remains a part of libgist.

   DEVNOTE 2: A "dynamic" barrier is also known as a clock. A phaser is
   another thread synchronization primitive similar to but more
   sophisticated and general than a clock. Our implementation of a
   dynamic barrier is very simple/simplistic.
*/

/*
   This file is part of libgist.

   libgist is free software; you can redistribute it and/or modify it
   under the terms of the GNU General Public License as published by the
   Free Software Foundation; either version 2 of the License, or (at your
   option) any later version.

   libgist is distributed in the hope that it will be useful, but WITHOUT
   ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
   FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
   for more details.

   You should have received a copy of the GNU General Public License
   along with libgist; if not, write to the Free Software Foundation,
   Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.
*/

/*
   REVISION HISTORY

   $HeadURL: http://libgist.googlecode.com/svn/branches/lazebnik_dev/src/dynamic_barrier.hh $
   $Id: dynamic_barrier.hh 176 2012-03-12 07:54:15Z libgist@gmail.com $
*/

#ifndef GIST_DYNAMIC_BARRIER_DOT_HH
#define GIST_DYNAMIC_BARRIER_DOT_HH

//------------------------------ HEADERS --------------------------------

// Boost
#include <boost/thread/locks.hpp>
#include <boost/thread/mutex.hpp>
#include <boost/thread/condition_variable.hpp>

#include <boost/utility.hpp>

// Standard C++
#include <algorithm>

//---------------------------- NAMESPACE --------------------------------

namespace gist {

//------------------------------- CLASS ---------------------------------

/**
   \brief A thread barrier (aka rendezvous) with a variable thread count.

   A thread barrier or rendezvous is a synchronization primitive that
   blocks all participating threads until each of them has "arrived" at
   the barrier. Once all threads have reached the barrier, it allows them
   all to proceed from that point on.

   Usually, a barrier is created for a specific number of threads and can
   only be used for that particular number of threads. However, in some
   situations, we would like to be able to change that number. For
   example, some threads may finish up their work and stop participating
   in the barrier. Alternatively, new threads may be spawned that may
   want to join a group of threads already participating in a barrier.

   This class implements a dynamic barrier as described in the preceding
   paragraph. Such a barrier is also known as a clock. A phaser is
   another thread synchronization primitive similar to but more
   sophisticated and general than a clock. Our implementation of a
   dynamic barrier (or clock) is very simple/simplistic.

   DEVNOTE: Boost.Thread already provides a barrier implementation.
   However, that is a "static" barrier, i.e., one whose thread count is
   fixed at creation time and cannot be changed. Ideally, we would like
   this file's class to be included in Boost.Thread. But for now, it
   remains a part of libgist.
*/
class dynamic_barrier: boost::noncopyable {
   /// This variable specifies the number of threads currently
   /// participating in the barrier.
   int m_count ;

   /// This is the count of threads that have arrived at the barrier.
   /// After all the currently participating threads have arrived, this
   /// class will automatically reset the count to zero so that the
   /// barrier becomes ready for use again.
   int m_arrived ;

   /// This variables keeps track of the number of threads currently
   /// waiting at the barrier. After all the participating threads have
   /// arrived, this count will start to go down as each thread resumes.
   /// The last thread to resume will reset the barrier (i.e., make the
   /// count of threads arrived zero).
   int m_waiting ;

   /// We use this condition variable to block threads as they arrive at
   /// the barrier and to wake them up when it's time to resume.
   boost::condition_variable m_cond ;

   /// The mutex that goes with the above variables.
   boost::mutex m_mutex ;

public:
   /**
      \brief  Initialize barrier.
      \param  n Initial number of threads participating in the barrier.
      \return Properly initialized thread barrier.

      On instantiation, clients should specify how many threads will
      initially participate in this barrier. This number can change
      later.

      NOTE: The number of participating threads must be greater than
      zero. This constructor will silently set the thread to count to one
      if you specify a non-positive initial count.

      NOTE 2: This class cannot be copied. You must pass it to
      participating threads via a reference or a pointer.
   */
   dynamic_barrier(int n)
      : m_count(std::max(1, n)), m_arrived(0), m_waiting(0)
   {}

   /**
      \brief  Wait for all threads to arrive at the barrier.
      \return Nothing.

      After a barrier has been created and passed to all participating
      threads, they must each call this method to "meet/sync up" with all
      their "siblings."

      Each thread that calls this function will block in that call until
      all the other participating threads have also called it. After all
      participating threads have arrived, all waiting threads will be
      able to proceed from the point where they called wait.
   */
   void wait() {
      // As each participating thread arrives, it will have to increment
      // the relevant counter.
      boost::unique_lock<boost::mutex> lock(m_mutex) ;
      ++m_arrived ;

      // The last thread to arrive doesn't need to wait
      if (m_arrived >= m_count) {
          m_cond.notify_all() ;
          return ;
      }

      // The early bird threads will have no choice but to block...
      ++m_waiting ;
      for(;;)
      {
         m_cond.wait(lock) ;

         // If we get past the above wait, then either the last thread
         // has arrived or the number of participating threads has
         // changed. In either situation, we have to check if it's time
         // to exit the barrier.
         if  (m_arrived >= m_count) {
            --m_waiting ;
            if (m_waiting <= 0) // last thread to exit barrier has to reset it
                m_waiting  = m_arrived = 0 ;
            return ;
         }
         //else: all threads have not yet arrived ==> continue waiting
      }
   }

   /**
      \brief  Update the number of participating threads.
      \param  delta Number of threads to add or remove.
      \return Nothing.

      This method implements the "dynamic" part of a dynamic barrier. It
      changes the number of participating threads by the specified delta
      and informs the currently waiting threads so they can decide
      whether to exit the barrier or continue waiting.
   */
   void update(int delta) {
      boost::lock_guard<boost::mutex> lock(m_mutex) ;
      m_count += delta ;
      if (m_count < 1)
          m_count = 1 ;
      m_cond.notify_all() ;
   }

   /// Convenience methods to update the thread count by +/-1.
   //@{
   void increment() {update(+1) ;}
   void decrement() {update(-1) ;}
   //@}
} ;

//-----------------------------------------------------------------------

} // namespace gist

#endif

/* So things look consistent in everyone's emacs... */
/* Local Variables: */
/* indent-tabs-mode: nil */
/* End: */
